package com.fr.lintcode;

import java.util.Arrays;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月15日
*时间：下午5:42:52
*/
public class Q89 {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    public int kSum(int A[], int k, int target) {
        Arrays.sort(A);
        int n = A.length;
        int dp[][][] = new int[n + 1][k + 1][target + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (j > i) {
                    break;
                }
                for (int p = A[0]; p <= target; p++) {
                    if (A[i - 1] > p) {
                        dp[i][j][p] = dp[i - 1][j][p];
                    } else if (A[i - 1] == p && j == 1) {
                        dp[i][j][p] = 1;
                    } else {
                        dp[i][j][p] = dp[i - 1][j][p] + dp[i - 1][j - 1][p - A[i - 1]];
                    }

                }
            }
        }
        return dp[n][k][target];
    }

    @Test
    public void testA() {
        int A[] = { 1, 2, 3, 4, 5, 6 };
        System.out.println(kSum(A, 2, 7));
    }
}
